93. 复原IP地址

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/restore-ip-addresses/

题目描述

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]

题目分析

本题同样也是回溯法的应用，只是本题要比之前的题目要稍微的多一些东西。
本题中需要多考虑的有几个点：

  1. 什么样的数字满足ip地址的格式
  • 0-255之间，并且不是以0开头的，比如010，强转是能转成int型的10的，但这是不符合ip数字格式的。
    所以在此处我们可以写一个函数，来判断当前的字符串是否满足ip地址的格式：
    1
    2
    3
    4
    5
    6
    7
    8
    def ip_validate(self, s):
        if not s:
            return False
        if len(s) > 1 and s[0] == '0':
            return False
        if int(s) < 0 or int(s) > 255:
            return False
        return True
  1. 树的深度一定是4
  • ip地址树的深度一定是4，也就是说一定是xxx.xxx.xxx.xxx构成的
  1. 子串的选取：
  • 同样为了满足ip地址的格式，子串长度一定是1-3之间的。这同样也是一种剪枝。

然后我们按照正常递归的逻辑来考虑：

  1. 递归结构
  2. 递归边界
  3. 递归参数

递归结构

本题的递归结构是：

和一般的递归结构没有太大的区别，需要注意的是w的选取要进行一定的剪枝，满足一定的限定条件。

递归边界

由于需要满足ip地址的格式，所以本题的递归边界是：

1
if n == 4:

递归参数

然后确定递归参数。
我们需要：

  • n：表示递归树的深度，也就是每次往前走一步的步数。
  • s：表示原字符串。
  • pos：表示字符串当前选取字串的开始位置，比如2252，第一步选取了2，那么pos=1，也就是下一次从位置1开始选取字串。
  • result：到达一次递归树叶子节点，也就是到达一次递归边界的一个解。
  • result_all：最终解。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def __init__(self):
        self.result_all = None
        
    def restoreIpAddresses(self, s: str) -> List[str]:
        self.result_all = []
        self.dfs(1, s, 0, [])
        return self.result_all
        
    def dfs(self, n, s, pos, result):
        if n == 4:
            if self.ip_validate(s[pos:]):
                result.append(s[pos:])
                self.result_all.append(".".join(result))
                result.pop()    
            return
        
        for i in range(pos + 1, pos + 4):
            sub_s = s[pos: i]
            if not self.ip_validate(sub_s):
                continue
            result.append(sub_s)
            self.dfs(n+1, s, i, result)
            result.pop()
        
        return
    
    def ip_validate(self, s):
        if not s:
            return False
        if len(s) > 1 and s[0] == '0':
            return False
        if int(s) < 0 or int(s) > 255:
            return False
        return True